package com.chj.jz.dp.class05;

public class Code02_ScrambleString {
	/**
     * @param s1: A string
     * @param s2: Another string
     * @return: whether s2 is a scrambled string of s1
     */
    public static boolean isScramble(String s1, String s2) {
    	char[] ss1 = s1.toCharArray();
    	char[] ss2 = s2.toCharArray();
        int m = ss1.length;
        int n = ss2.length;
        if (m != n) {
            return false;
        }

        boolean[][][] f = new boolean[n][n][n + 1];
        int i, j, k, w;
        // initialization: length = 1
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                f[i][j][1] = (ss1[i] == ss2[j]);
            }
        }

        for (k = 2; k <= n; k++) {
            for (i = 0; i <= n - k; i++) { // S[i...i+len-1]
                for (j = 0; j <= n - k; j++) { // T[j..j+len-1]
                    f[i][j][k] = false;
                    // break into S1 and S2
                    // S1 has length w, S2 has length len - w
                    for (w = 1; w <= k - 1; w++) {
                        // no swap
                        // S1-->T1, S2 --> T2
                        if (f[i][j][w] && f[i + w][j + w][k - w]) {
                            f[i][j][k] = true;
                            break;
                        }
                    }
                        // swap
                        // S1 --> T2, S2 --> T1
                    for (w = 1; w <= k - 1; w++) {
                        if (f[i][j + k - w][w] && f[i + w][j][k - w]) {
                            f[i][j][k] = true;
                            break;
                        }
                    }
                }
            }
        }

        return f[0][0][n];
    }
    
    public static void main(String[] args) {
//    	输入: s1 = "great", s2 = "rgeat"
		{
			String str1 = "great";
			String str2 = "rgate";
			System.out.println(isScramble(str1, str2));
		}
		{
			String str1 = "a";
			String str2 = "b";
			System.out.println(isScramble(str1, str2));
		}
    }
}
